#include <vector>
#include <iostream>

// #11 盛最多水的容器

// 暴力解法
namespace S1 {
    class Solution {
    public:
        int maxArea(std::vector<int>& height) {
            int max = 0;
            for (int i = 0; i < height.size(); i++) {
                for (int j = i + 1; j < height.size(); j++) {
                    int min = std::min(height[i], height[j]);
                    if (((j - i) * min) > max) {
                        max = (j - i) * min;
                    }
                }
            }
            return max;
        }
    };
}

// 双指针
namespace S2 {
    class Solution {
    public:
        int maxArea(std::vector<int>& height) {
            int max = 0;
            int left = 0, right = height.size() - 1;
            while (left != right) { // 两个指针相遇
                
                bool isLeft = false;
                int min = 0;
                if (height[left] <= height[right]) {
                    min = height[left];
                    isLeft = true;
                } else {
                    min = height[right];
                    isLeft = false;
                }
                // 计算当前指针位置形成的容器容量
                if ((right - left) * min > max) {
                    max = (right - left) * min; // 更新最大容量
                }

                // 移动高度较小的指针(因为容器的容量受限于较短的线， 移动较短的线有可能找到更高的钱)
                if (isLeft) {
                    left ++;
                } else {
                    right --;
                }
            }
            
            return max;
        }
    };
}

int main(){
    std::vector<int> height {1,8,6,2,5,4,8,3,7};
    S2::Solution s;
    int res = s.maxArea(height);
    std::cout << res << std::endl;
}